package com.expires.leecode;

import com.expires.leecode.bean.ListNode;

import java.util.*;

/**
 * @program: SpringBootDemos
 * @description:
 * @author: Kangsen
 * @create: 2022-05-27 16:28
 **/
public class Solution {

    /**
     * 面试题 17.11. 单词距离  https://leetcode.cn/problems/find-closest-lcci/
     */
    public static int findClosest(String[] words, String word1, String word2) {
        //暴力硬解
        /*List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if(words[i].equalsIgnoreCase(word1)){
                list1.add(i);
            }
            if(words[i].equalsIgnoreCase(word2)){
                list2.add(i);
            }
        }
        List<Integer> list = new ArrayList();
        for (int i = 0; i < list1.size() ; i++) {
            for (int j = 0; j < list2.size() ; j++) {
                list.add(Math.abs(list1.get(i) - list2.get(j)));
            }
        }
        list = list.stream().sorted((o1,o2)->o1.compareTo(o2)).collect(Collectors.toList());
        if(list.size() > 0){
            return list.get(0);
        }
        return -1;*/

        //双指针
        int p1 = -1;
        int p2 = -1;
        int minLen = Integer.MAX_VALUE;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equalsIgnoreCase(word1)) {
                p1 = i;
            } else if (words[i].equalsIgnoreCase(word2)) {
                p2 = i;
            }

            if (p1 != -1 && p2 != -1) {
                minLen = Math.min(minLen, Math.abs(p1 - p2));
            }
        }
        return minLen;
    }

    /**
     * 删除最外层的括号   https://leetcode.cn/problems/remove-outermost-parentheses/
     */
    public static String removeOuterParentheses(String s) {
        String result = "";
        int position = 0;
        int len = s.length();
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < len; i++) {
            //System.out.println(s.charAt(i));
            char c = s.charAt(i);
            if (c == '(') {
                position += 1;
            } else if (c == ')') {
                position -= 1;
            }
            stringBuilder.append(c);
            if (position == 0) {
                //说明当前位置的后一位需要添加加号
                stringBuilder.append('+');
            }
        }
        stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        System.out.println(stringBuilder);
        String[] strings = stringBuilder.toString().split("\\+");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < strings.length; i++) {
            System.out.println(strings[i]);
            sb.append(strings[i].substring(1, strings[i].length() - 1));
        }
        result = sb.toString();
        return result;
    }

    /**
     * https://leetcode.cn/problems/validate-ip-address/
     *
     * @param queryIP ip地址校验
     * @return
     */
    public static String validIPAddress(String queryIP) {
        String result = "Neither";
        try {
            if (queryIP == null || queryIP.equalsIgnoreCase("")) {
                return result;
            }
            //以其他非数字 字母开头
            char startChar = queryIP.charAt(0);
            if (!Character.isDigit(startChar) && !(Character.toLowerCase(startChar) >= 'a' && Character.toLowerCase(startChar) <= 'f')) {
                return result;
            }
            char endChar = queryIP.charAt(queryIP.length() - 1);
            if (!Character.isDigit(endChar) && (!(Character.toLowerCase(endChar) >= 'a') || !(Character.toLowerCase(endChar) <= 'f'))) {
                return result;
            }
            //判断IPV4还是V6
            if (queryIP.contains(".")) {//判断IPV4
                String[] split = queryIP.split("\\.");
                if (split.length == 4) {
                    for (String s : split) {
                        if ((s.length() > 1 && s.startsWith("0")) || 0 > Integer.parseInt(s) || Integer.parseInt(s) > 255) {
                            return result;
                        }
                    }
                    result = "IPv4";
                }
            } else if (queryIP.contains(":")) {//判断IPv6
                String[] split = queryIP.split("\\:");
                if (split.length == 8) {
                    for (int i = 0; i < split.length; i++) {
                        if (split[i].equalsIgnoreCase("")) {
                            return result;
                        }
                        if (1 > split[i].length() || split[i].length() > 4) {
                            return result;
                        }
                        for (int j = 0; j < split[i].length(); j++) {
                            char c = split[i].charAt(j);
                            //非数字 并且 不在a-f中
                            //if(!Character.isDigit(c) && !((Character.toLowerCase(c) >= 'a') || !(Character.toLowerCase(c) <= 'f')) ){
                            if (!Character.isDigit(c) && !(Character.toLowerCase(c) >= 'a' && Character.toLowerCase(c) <= 'f')) {
                                return result;
                            }
                        }
                    }
                    result = "IPv6";
                }
            }
        } catch (NumberFormatException e) {
            //e.printStackTrace();
            result = "Neither";
        }
        return result;
    }

    /**
     * 两数相加  https://leetcode.cn/problems/add-two-numbers/
     * 2  -> 4 ->  3
     * 5  -> 6 ->  4
     * <p>
     * 7  -> 0 ->  8
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //加数1栈
        Stack<Integer> add1Stack = readListNode(l1, true);
        System.out.println(add1Stack);
        //加数2栈
        Stack<Integer> add2Stack = readListNode(l2, true);
        System.out.println(add2Stack);
        //溢出进位栈
        Stack<Integer> overflowStack = new Stack<>();
        //结果栈
        Stack<Integer> resultStack = new Stack<>();
        Queue<Integer> resultQueue = new ArrayDeque();
        while (add1Stack.size() > 0 || add2Stack.size() > 0 || overflowStack.size() > 0) {
            int sum = 0;
            if (add1Stack.size() > 0) {
                sum += add1Stack.pop();
            }
            if (add2Stack.size() > 0) {
                sum += add2Stack.pop();
            }
            if (overflowStack.size() > 0) {
                sum += overflowStack.pop();
            }
            if (sum > 9) {
                resultStack.push(sum % 10);
                resultQueue.add(sum % 10);
                overflowStack.push(sum / 10);
            } else {
                resultStack.push(sum);
                resultQueue.add(sum);
            }
        }
        System.out.println(resultStack);
        //ListNode listNode = buildListNode(resultStack);
        ListNode listNode = buildListNode(resultQueue);
        return listNode;
    }

    public static ListNode buildListNode(Stack<Integer> stack) {
        ListNode resultListNode = null;
        if (stack.size() > 0) {
            resultListNode = new ListNode(stack.pop(), buildListNode(stack));
        }
        return resultListNode;
    }

    public static ListNode buildListNode(Queue<Integer> queue) {
        ListNode resultListNode = null;
        if (queue.size() > 0) {
            resultListNode = new ListNode(queue.poll(), buildListNode(queue));
        }
        return resultListNode;
    }

    public static Stack<Integer> readListNode(ListNode l1, boolean isReverse) {
        Stack<Integer> addStack = new Stack<>();
        ListNode tmp = l1;
        if (isReverse) {//逆序: 先进链表尾数据
            List<ListNode> list = new ArrayList<>();
            list.add(tmp);
            while (tmp.getNext() != null) {
                tmp = tmp.getNext();
                list.add(tmp);
            }
            for (int i = list.size() - 1; i >= 0; i--) {
                addStack.push(list.get(i).getVal());//入栈最底层的节点数
            }
        } else {//顺序 正序进栈
            while (tmp != null) {
                addStack.push(tmp.getVal());
                tmp = tmp.getNext();
            }
        }
        return addStack;
    }


    /**
     * 剑指 Offer II 114. 外星文字典 https://leetcode.cn/problems/Jf1JuT/
     *
     * @param words
     * @return
     */
    public String alienOrder(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if (map.containsKey(words[i])) {
            }
        }
        return null;
    }


    /**
     * 无重复字符的最长子串 https://leetcode.cn/problems/longest-substring-without-repeating-characters/
     *
     * @param s
     * @return
     */

    /***
     * a b c a b c b b
     * stringBuilder的内容
     * abc
     *  bca
     *    cab
     *      cb
     *        b
     *
     */
    public static int lengthOfLongestSubstring(String s) {
        /*if (s.equalsIgnoreCase("")) {
            return 0;
        }
        //StringBuilder 方式
        int len = s.length();
        int max = 0;
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (i != 0) {
                int indexOf = stringBuilder.indexOf(String.valueOf(c));
                if (indexOf != -1) {//存在
                    stringBuilder = new StringBuilder(stringBuilder.substring((indexOf + 1), stringBuilder.length()));
                }
            }
            stringBuilder.append(c);
            max = Math.max(max, stringBuilder.length());
            System.out.println(stringBuilder);
        }
        return Math.max(max, stringBuilder.length());*/


        int minIndex = 0;
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (s.indexOf(c, minIndex) < i) {
                minIndex = s.indexOf(c, minIndex) + 1;
            } else {
                ans = Math.max(ans, i - minIndex + 1);
            }
        }
        return ans;

        //return -1;
    }

    /**
     * 火柴拼正方形 https://leetcode.cn/problems/matchsticks-to-square/
     *
     * @param matchsticks
     * @return
     */
    public static boolean makesquare(int[] matchsticks) {
        if (matchsticks.length <= 3) {
            return false;
        }
        int sum = 0;
        for (int i = 0; i < matchsticks.length; i++) {
            sum += matchsticks[i];
        }
        //和不能被4整除的一定不行
        if (sum % 4 != 0) {
            return false;
        }
        //int[] ints = quickSort(matchsticks, 0, matchsticks.length - 1);
        Arrays.sort(matchsticks);
        //接下来就要去 寻找能成为正方形的集合： 正方形周长就是数组的sum,四条边满足 sum/4,因此只要能把数组所有内容均分成4个数 每个数为sum/4
        int[] arr = new int[matchsticks.length];//位置调换一下  大数放前面来
        for (int i = matchsticks.length - 1, j = 0; i >= 0 && j < matchsticks.length; i--, j++) {
            if (matchsticks[i] > (sum / 4)) {//当有某一元素大于边长 这肯定就不行
                return false;
            }
            arr[j] = matchsticks[i];
        }
        //定义4个桶
        int[] bucket = new int[4];
        //return dfs(0,arr,bucket,sum/4);

        //return search(arr,sum);
        return brackTrack(arr, sum / 4, bucket, 0);
    }

    /**
     * 是否能组成正方形
     *
     * @param arr 数组
     * @param sum 正方形周长
     * @return
     */
    public static boolean search(int[] arr, int sum) {
        //边长
        int sideLen = sum / 4;
        //4个桶  每个桶的数据要加到边长的数据
        int[] bucket = new int[4];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < bucket.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[j] == 0) {
                    continue;
                }
                bucket[i] += arr[j];
                if (bucket[i] == sideLen) {
                    arr[j] = 0;
                    break;//找下一个桶
                } else {
                    if (bucket[i] > sideLen) {
                        //加了一个 超过边长了 就退回一下 加下一个
                        bucket[i] -= arr[j];
                    }
                }

                if ((j == arr.length - 1) && (bucket[i] != sideLen)) {
                    //本次就加完了还没有

                    return false;
                }

                /*
                bucket[i] += arr[j];
                stack.push(arr[j]);
                arr[j] = 0;
                //将已经使用的元素从当前数组中移除
                if(bucket[i] == sideLen){
                    break;
                }else{
                    if(bucket[i] > sideLen){
                        //加了一个 超过边长了 就退回一下 加下一个
                        arr[j] = stack.pop();
                        bucket[i] -= arr[j];
                    }
                }
                if((j == arr.length - 1) && (bucket[i] != sideLen)){
                    return false;
                }*/
            }
            if (i == bucket.length - 1) {
                return true;
            }
        }
        return false;
    }

    /*按照题意分到四个桶中，使的四个桶和相等，等同于集合划分问题！
    剪枝一、递减排序,使得更好的命中回溯中的第一个continue的判断条件，即if(bucket[i] + arr[index] > target)continue;//去下一个桶
    剪枝二：表示说如果前面做出的选择之后，递归却没有找到任何一个合适的使得之和==target，那么撤销选择后一定为0，这个时候可以直接return false；
    举例：桶中加入7，target=8，但是递归完所有的火柴，不存在一个长度为1的，那么撤销选择后就为0了！*/
    public static boolean brackTrack(int[] arr, int target, int[] bucket, int index) {
        //basecase 递归到最后，所有火柴都加入桶
        if (index == arr.length) {
            for (int t : bucket) {
                if (t != target) {
                    return false;
                }
            }
            return true;
        }
        //选择列表：四个桶
        for (int i = 0; i < 4; i++) {
            if (bucket[i] + arr[index] > target) {
                continue;//去下一个桶
            }
            //递归前做选择
            bucket[i] += arr[index];
            if (brackTrack(arr, target, bucket, index + 1)) {
                return true;
            }
            //递归后撤销选择
            bucket[i] -= arr[index];
            if (bucket[i] == 0) {
                //剪枝二、表示说如果前面做出的选择之后，递归却没有找到任何一个合适的使得之和==target，那么撤销选择后一定为0，
                //这个时候可以直接return false；举例：桶中加入7，target=8，但是递归完所有的火柴，不存在一个长度为1的，
                // 那么撤销选择后就为0了！
                return false;
            }
        }
        return false;
    }

    //深度遍历
    public static boolean dfs(int index, int[] arr, int[] bucket, int len) {
        if (index == arr.length) {
            return true;
        }
        for (int i = 0; i < bucket.length; i++) {
            //将数组加到当前桶中
            bucket[i] += arr[index];
            if (bucket[i] <= len) {
                //桶中数据量
                if (bucket[i] == len) {
                    //刚好等于边长了

                } else {
                    //还未达到边长

                }
            } else {

            }
            //该桶中数据长度等于边长了
            /*if (bucket[i] <= len && dfs(index + 1, arr, bucket, len)) {
                return true;
            }
            bucket[i] -= arr[index];*/
        }
        return false;
    }

    /**
     * 回文数
     *
     * @param x
     * @return
     */
    public static boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        /*String str = String.valueOf(x);
        int len = str.length();
        for (int i = 0,j = len-1; i < j; i++,j--) {
            char begin = str.charAt(i);
            char end = str.charAt(j);
            if(!String.valueOf(begin).equals(String.valueOf(end))){
                return false;
            }
        }
        return true;*/
        int tmp = x;
        int result = 0;
        while (tmp != 0) {
            result = result * 10 + tmp % 10;
            tmp = tmp / 10;
        }
        return result == x;
    }


    /**
     * Z字形变换  https://leetcode.cn/problems/zigzag-conversion/
     *
     * @param s
     * @param numRows
     * @return
     */
    public static String convert(String s, int numRows) {
        /*int len = s.length();
        System.out.println("numRows=> " + numRows + " s.len =》" + len);
        if (len == 0) {
            return null;
        }
        //计算一下需要多少列
        int column = len / (3 * numRows - 2);
        if (len % (3 * numRows - 2) > 0) {
            //需要几组row列
            column += 1;
        }
        char[][] resultArray = new char[numRows][column * numRows];
        //将字符串的存储转为二维数组
        for (int i = 0; i < s.length(); i++) {
            int currentColumn = i == 0 ? 0 : (i % (numRows + (numRows - 2)));
            //计算x,y位置索引值
            int x = -1;
            int y = -1;
            if (currentColumn >= 0 && currentColumn < numRows) {
                //整行数据
                System.out.println("整行都是数据");
                // 每组数据的数据量  numRows + (numRows - 2) ===> 2 * numRows - 2
            } else {
                //单行数据
                System.out.println("单行一个数据");
            }
            System.out.println("i = " + i + " => (" + x + "," + y + ")");
            //计算一下当前这字符放哪个位置
            //resultArray[x][y] = s.charAt(i);
        }*/
        if(s.equalsIgnoreCase("") || numRows == 1){
            return s;
        }
        List<StringBuilder> list = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            list.add(new StringBuilder());
        }
        //flag 反向
        int flag = -1;
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            list.get(index).append(s.charAt(i));
            if(index == 0 || (numRows -1 == index)){//flag仅是变向作用
                flag = -flag;
            }
            index += flag;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i));
        }
        return sb.toString();
    }

    /**
     * 反转数  122-》221
     *
     * @param num
     * @return
     */
    public static int returnNum(int num) {
        int result = 0;
        while (num != 0) {
            result = result * 10 + num % 10;
            num = num / 10;
        }
        return result;
    }

    /**
     * 正整数反转 https://leetcode.cn/problems/reverse-integer/
     * @param x
     * @return
     */
    public static int reverse(int x) {
        //-231 <= x <= 231 - 1
        if (x == Integer.MIN_VALUE)
            return 0;
        int result = 0;
        while(x != 0){
            if (result > Integer.MAX_VALUE / 10 || result < Integer.MIN_VALUE / 10)  {
                return 0;
            }
            result = result * 10 +  x % 10;
            x /= 10;
        }
        if(x < 0){
            result = -result;
        }
        return result;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * calculate combination Number
     * @param r int整型
     * @param n int整型
     * @return int整型
     */
    public static int combination (int r, int n) {
        // write code here
        return factorial(n) / factorial(r) / factorial(n - r);
    }

    /**
     * 阶乘
     * @param n
     */
    public static int factorial(int n){
        if(n == 0){
            return 1;
        }
        if(n < 0){
            return 0;
        }
        int sum = 1;
        for (int i = 1; i <= n; i++) {
            sum *= i;
        }
        return sum;
    }

    public static int[] arrayMerge (int[] array1, int n, int[] array2, int m) {
        // write code here
        List<Integer> list = new ArrayList<>(n+m);
        for (int i = 0; i < array1.length; i++) {
            list.add(array1[i]);
        }
        for (int i1 = array2.length - 1; i1 >= 0; i1--) {
            list.add(array2[i1]);
        }
        //list = list.stream().sorted(((o1, o2) -> o1.compareTo(o2))).collect(Collectors.toList());

        int[] result = new int[m+n];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        Arrays.sort(result);
        return result;
    }

    /**
     * 爱吃香蕉的珂珂 https://leetcode.cn/problems/koko-eating-bananas/
     * @param piles
     * @param h
     * @return
     */
    public static int minEatingSpeed(int[] piles, int h) {

        return -1;
    }

    /**
     * 盛最多水的容器 https://leetcode.cn/problems/container-with-most-water/
     * @param height
     * @return
     */
    public static int maxArea(int[] height) {
        //暴力枚举
        //最大面积
        /*int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            for (int i1 = 0; i1 < height.length; i1++) {
                if(i != i1){
                    //计算面积
                    int area = Math.min(height[i], height[i1]) * (Math.abs(i - i1));
                    maxArea = Math.max(area, maxArea);
                }
            }
        }
        */

        //双指针
        int i = 0, j = height.length -1, maxArea = 0;
        while (i < j){
            //左边小的情况下就往右移动头指针反之就往左移动指针
            maxArea = height[i] < height[j] ? Math.max(maxArea, (j - i)*height[i++]) : Math.max(maxArea, (j - i)*height[j--]);
        }
        return maxArea;
    }

    /**
     * 整数转罗马数字  https://leetcode.cn/problems/integer-to-roman/
     * @param num
     * @return
     */
    public static String intToRoman(int num) {
        StringBuilder result=new StringBuilder();
        if(1 <= num && num <=3999){
            int[] values={1000,900,500,400,100,90,50,40,10,9,5,4,1};
            String[] rom={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
            for(int i=0;i<values.length;i++){
                while(num>=values[i]){
                    result.append(rom[i]);
                    num-=values[i];
                }
            }
        }
        return result.toString();
    }

    /**
     * 罗马数字转整数
     * @param s
     * @return
     */
    public static int romanToInt(String s) {
        Map<String,Integer> map = new HashMap<>();
        map.put("M",1000);
        map.put("D",500);
        map.put("C",100);
        map.put("L",50);
        map.put("X",10);
        map.put("V",5);
        map.put("I",1);
        int result = 0;
        int last = Integer.MAX_VALUE;
        int curr = 0;
        for (int i = 0; i < s.length(); i++) {
            String s1 = String.valueOf(s.charAt(i));
            if(map.containsKey(s1)){
                curr = map.get(s1);
                if(curr > last){
                    //这里乘2是因为上一步多加了一遍 但是上一步没有判断出来 因此这一步就多减一遍 把上次加的减掉
                    result += (curr - 2 * last);
                }else{
                    result += curr;
                }
                last = curr;
            }
        }
        return result;
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList();
        if(nums.length < 3){
            return list;
        }
        /*for (int i = 0; i < nums.length; i++) {
            for (int i1 = (i+1); i1 < nums.length; i1++) {
                for (int i2 = (i1 +1); i2 < nums.length; i2++) {
                    if(nums[i] + nums[i1] + nums[i2] == 0){
                        List<Integer> tmp = new ArrayList();
                        tmp.add(nums[i]);
                        tmp.add(nums[i1]);
                        tmp.add(nums[i2]);
                        list.add(tmp);
                    }
                }
            }
        }*/

        /*for (int i = 0; i < nums.length - 3; i++) {
            if(nums[i] + nums[i+1] + nums[i+2] == 0){
                List<Integer> tmp = new ArrayList();
                tmp.add(nums[i]);
                tmp.add(nums[i+1]);
                tmp.add(nums[i+2]);
                list.add(tmp);
                i += 2;
            }
        }*/
        System.out.println(list);
        return null;
    }

    public static void main(String[] args) {
        /*String[] atr = new String[]{"k","c","ur","jm","jh","dl","sa","qw","tqr","b","kl","hns","g","y","au","ksw","zy","mi","u","hne","n","ub","irq","na","k","sg","np","fi","hyd","p","aoi","ixp","ve","ll","yh","dh","qc","yg","ic","ef","ho","ueq","w","pb","b","bnd","ahe","jbf","gui","jsu","wo","m","pzj","g","o","xoa","l","uwm","kdp","ra","v","p","mq","s","cpm","f","ma","vyd","p","kzw","oa","k","qm","ifg","dlw","y","y","ml","adg","mkw","vjr","yxw","x","s","rfv","pb","w","rq","gun","aaf","x","jj","lp","lb","nk","q","xa","r","ku","ecq","m","zd","zra","zee","x","klx","tzb","lwe","d","y","r","u","o","y","n","ah","pcv","g","y","uj","pu","pyz","ee","gc","n","t","r","lhu","f","uw","h","gfc","s","j","ixi","zvk","uyy","ga","b","wzn","u","pst","vq","u","pdn","zsn","vxk","msn","in","ev","ozq","w","p","u","p","f","hg","iab","gu","a","cih","m","qai","mzs","ol","wu","xhm","sch","hf","kfw","iq","opa","t","g","ym","il","z","a","xw","noo","jxk","th","j","ifi","kx","nas","m","xvy","g","jcn","sg","t","g","hz","z","oc","kvy","j","x","t","vel","tf","vw","fvq","l","u","uml","ksy","tbl","xan","o","s","v","zhe","oo","u","bc","je","xo","k","ame","me","tux","to","vzk","v","k","khz","hng","cg","thb","qt","vez","x","gbh","d","csc","sc","vl","cky","zb","g","wn","snn","de","syl","rl","cah","p","nj","vs","u","id","zx","v","lb","w","qxg","urw","yt","q","dyo","yxo","fi","p","iyi","cyk","ys","ff","os","uuc","p","egr","dra","hb","cpi","rll","j","o","dez","zq","z","ny","hc","jq","cpz","ih","n","qo","xv","gm","rg","vfi","rj","apy","c","x","cca","y","w","bf","d","sj","iyp","qb","mb","p","sbc","q","gp","wrv","v","nt","xw","e","x","uvy","wgm","i","w","uyg","z","py","ybd","gew","uzp","y","a","bwd","a","h","hpa","fid","q","d","t","n","ik","gm","lo","suo","wfe","vaj","l","vkp","yw","v","jr","psn","bu","o","p","zf","ej","d","yan","x","x","tkw","xxy","ehr","b","ds","z","ncq","l","qm","qb","uzc","do","k","f","kz","je","r","b","aq","hz","k","ipv","v","bai","c","fu","s","pg","ctn","i","fw","vu","hej","xl","qtv","nn","wal","fd","iay","kf","t","vv","fu","b","z","udg","ypg","rx","e","wus","fh","c","f","q","ijv","vl","hh","po","sf","sl","t","acm","hp","m","z","rrx","r","b","na","g","bt","nmx","edo","gau","s","j","k","y","ph","fl","xv","n","hua","i","kzo","lgz","fpq","mvh","yf","jvc","out","uv","w","bpk","k","xx","gbn","kj","yq","z","ul","mz","dxr","onc","nfu","mla","kyw","n","v","l","nly","qz","t","kbz","bj","ovy","xmr","k","ugo","ri","s","wt","l","muf","k","b","gs","w","dj","vb","ieu","b","c","kj","vr","q","dy","udj","v","vwx","ny","m","if","xbr","yar","q","erl","wl","o","xsb","b","zx","gqs","jz","ozd","h","ny","ogm","qor","bg","her","hqt","qe","o","g","ov","iqv","p","p","cgh","oxx","j","m","ii","mw","itg","uo","i","ua","r","j","dch","wwb","nf","euf","em","x","huo","m","ro","quu","zl","i","tf","a","fx","x","kif","vx","l","rtx","kwf","w","yr","rkx","uur","m","ooz","co","dz","s","zs","ac","r","ty","jn","x","fti","j","tk","g","bff","p","dy","e","wr","tj","h","ee","bx","kw","rvs","xpz","yb","f","f","yym","hf","owh","mdz","thg","lb","f","erz","hjh","cy","tv","w","k","dsb","pa","j","q","pip","vmf","zet","k","gzs","pee","y","zgu","b","xf","pte","l","pq","pj","lzu","jwy","wgw","v","xfm","jyk","piy","gvo","pur","hzc","g","nvz","ox","kkr","do","kop","r","pd","ixk","y","qio","hf","yq","tnk","ga","g","dkj","yj","w","j","bl","e","g","ki","s","pwj","j","ju","sji","kh","mvq","hsh","k","d","qtq","rb","k","gd","n","xei","q","w","wz","esa","blf","kqk","l","bp","z","t","s","p","thx","jl","y","la","du","vdd","x","a","xhx","rp","hi","pb","b","z","aa","pug","us","tkt","y","w","tre","ie","mss","u","tg","dfj","h","ulo","dkp","o","bd","bqh","qx","fl","xm","a","uxm","nt","p","wc","tk","fr","sd","f","xj","eds","gc","xz","qqq","nfn","x","lm","q","ofr","jm","l","coh","pl","nx","x","yg","t","aip","zg","jtc","u","er","i","j","ph","z","j","ynt","wq","imb","gpe","til","ns","pyy","hq","qm","k","lp","o","j","vup","qfd","ohj","z","gg","bw","m","fii","fa","y","p","yaz","i","ig","of","p","ws","orp","arf","ru","urq","g","u","zg","zmh","wgx","l","b","bc","th","pe","d","juo","qq","jeu","w","j","yl","l","q","vki","al","n","hpb","pjo","ft","x","aal","hx","n","y","wgl","u","avy","l","wlw","bc","iik","hxj","icx","lp","qf","f","jay","eqs","nlf","yol","umb","s","ir","em","z","o","bip","f","syg","ep","wfy","ct","wuc","ccs","wsp","wej","en","g","bg","msi","yo","ba","s","iqw","mcs","kua","z","mwv","aa","tf","cvt","aox","q","my","g","h","gha","oz","g","l","iu","sza","td","pf","mi","mz","me","pt","bje","r","q","l","xcp","wz","bhc","sa","hq","or","qi","rv","x","vgx","q","es","fj","j","p","m","q","nqx","ay","hb","vn","km","zw","pxz","j","l","zx","aa","t","a","rr","glo","iqn","gm","s","nbu","e","pf","tfs","i","ly","rkv","a","pz","hl","okl","qfn","wr","zu","qg","a","a","dl","euz","lqi","egm","bgs","zv","bo","s","dx","m","r","xf","ij","gu","h","dm","qor","lne","ln","kz","s","ry","ml","n","kq","sz","nyx","m","s","pa","w","sbz","kxz","muz","bbw","fa","b","mb","oe","wve","tga","qi","re","hkf","jlj","vx","gg","glm","o","kvl","vvk","yfn","lt","c","kz","p","bq"};
        int closest = findClosest(atr, "bx","rx");
        System.out.println(closest);*/
        //String s = "(()())(())";
        //System.out.println(removeOuterParentheses(s));
        //"2001:0db8:85a3:0000:0000:8a2e:0370:7334"
        //"2001:db8:85a3:0:0:8A2E:0370:7334"
        //System.out.println(validIPAddress("2001:0db8:85a3:0000:0000:8a2e:0370:7334"));
        //System.out.println(validIPAddress("2001:db8:85a3:0:0:8A2E:0370:7334"));
        //System.out.println(validIPAddress("1e1.4.5.6"));
        //System.out.println(validIPAddress("2001:0db8:85a3::8A2E:037j:7334"));
        //System.out.println(validIPAddress("2001:0db8:85a3:0:0:8A2E:0370:7334:"));
        //System.out.println(validIPAddress("02001:0db8:85a3:0000:0000:8a2e:0370:7334"));

        /* ListNode l1 = new ListNode(2,new ListNode(4,new ListNode(3)));
        ListNode l2 = new ListNode(5,new ListNode(6,new ListNode(4)));
        ListNode l3 = new ListNode(0);
        ListNode l4 = new ListNode(0);
        ListNode l5 = new ListNode(9,new ListNode(9,new ListNode(9 ,new ListNode(9,new ListNode(9,new ListNode(9,new ListNode(9)))))));
        ListNode l6 = new ListNode(9,new ListNode(9,new ListNode(9 ,new ListNode(9))));
        addTwoNumbers(l5,l6);*/
        //System.out.println(lengthOfLongestSubstring("abcabcbb"));
        //System.out.println(lengthOfLongestSubstring("bbbbb"));
        //System.out.println(lengthOfLongestSubstring("pwwkew"));
        //System.out.println(lengthOfLongestSubstring(" "));
        //System.out.println(lengthOfLongestSubstring("dvdf"));
        //System.out.println(lengthOfLongestSubstring("cdd"));
        //System.out.println(lengthOfLongestSubstring("abcb"));

        //System.out.println(makesquare(new int[]{5,4,4,3,3,2,2,1}));
        //System.out.println(makesquare(new int[]{5,5,5,5,4,4,4,4,3,3,3,3}));
        /*System.out.println(isPalindrome(101));
        System.out.println(isPalindrome(121));
        System.out.println(isPalindrome(-121));
        System.out.println(isPalindrome(10));*/
        /*System.out.println(returnNum(472));
        System.out.println(returnNum(101));
        System.out.println(returnNum(121));
        System.out.println(returnNum(12345));
        System.out.println(returnNum(10));*/

        //System.out.println(convert("AB", 1));
                                      //-2147483648
        //System.out.println(reverse(-2147483412));
        //System.out.println(combination(2,3));
        //System.out.println(arrayMerge(new int[]{1, 2, 4, 5},4,new int[]{6}, 1));


        /*System.out.println(maxArea(new int[]{1,8,6,2,5,4,8,3,7}));
        System.out.println(maxArea(new int[]{1,1}));*/

        //System.out.println(intToRoman(1250));

        /*System.out.println("III >>> " + romanToInt("III"));
        System.out.println("IV >>> " + romanToInt("IV"));
        System.out.println("IX >>> " + romanToInt("IX"));
        System.out.println("LVIII >>> " + romanToInt("LVIII"));
        System.out.println("MCMXCIV >>> " + romanToInt("MCMXCIV"));*/



        int[] a = new int[]{-1,0,1,2,-1,-4};
        threeSum(a);
    }
}
